{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Description：\n",
    "这个笔记本尝试实现一下项亮推荐系统实践里面的UserCF算法， 采用的数据集是GroupLens提供的MovieLens的其中一个小数据集ml-latest-small。 该数据及包含700个用户对带有6100个标签的10000部电影的100000条评分。 该数据集是一个评分数据集， 用户可以给电影评5个不同等级的分数(1-5)， 而由于我们主要是研究隐反馈数据中的topN推荐问题， 所以忽略了数据集中的评分记录。  **TopN推荐的任务是预测用户会不会对某部电影评分， 而不是预测用户在准备对某部电影评分的前提下给电影评多少分**， 下面我们开始， 从逻辑上看， 其实这个任务主要分为下面的步骤：\n",
    "1. 导入数据， 读取文件得到\"用户-电影\"的评分数据， 并且分为训练集和测试集\n",
    "2. 计算用户之间的相似度\n",
    "3. 针对目标用户u， 找到其最相似的k个用户， 产生N个推荐\n",
    "4. 产生推荐之后， 通过准确率、召回率和覆盖率等进行评估。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-20T13:23:41.772738Z",
     "start_time": "2020-08-20T13:23:41.769746Z"
    }
   },
   "outputs": [],
   "source": [
    "import random\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "import math\n",
    "from operator import itemgetter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 读入数据\n",
    "读取文件得到\"用户-电影\"的评分数据， 并且分为训练集和测试集， 这里的思想是首先给出数据存在的路径， 然后通过pandas读取数据， 然后遍历该数据集， 把相应的数据存放到字典中， 这里之所以会用字典， 是因为用户对电影的评分会存在大量的稀疏。 所以我们依然需要建立一个\"{用户：{电影: 评分}}\"的这样一个字典， 后面基于这个字典去计算相似度。 如果感觉下面的代码理解有困难， 可以先参考我给出的博客链接补一下基础。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-20T13:25:12.752158Z",
     "start_time": "2020-08-20T13:25:12.705697Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>userId</th>\n",
       "      <th>movieId</th>\n",
       "      <th>rating</th>\n",
       "      <th>timestamp</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>4.0</td>\n",
       "      <td>964982703</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>4.0</td>\n",
       "      <td>964981247</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>6</td>\n",
       "      <td>4.0</td>\n",
       "      <td>964982224</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>47</td>\n",
       "      <td>5.0</td>\n",
       "      <td>964983815</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>50</td>\n",
       "      <td>5.0</td>\n",
       "      <td>964982931</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   userId  movieId  rating  timestamp\n",
       "0       1        1     4.0  964982703\n",
       "1       1        3     4.0  964981247\n",
       "2       1        6     4.0  964982224\n",
       "3       1       47     5.0  964983815\n",
       "4       1       50     5.0  964982931"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data_path = './ml-latest-small/'\n",
    "data = pd.read_csv(data_path+'ratings.csv')\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-20T13:26:11.018327Z",
     "start_time": "2020-08-20T13:26:10.938845Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th>movieId</th>\n",
       "      <th>1</th>\n",
       "      <th>2</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "      <th>5</th>\n",
       "      <th>6</th>\n",
       "      <th>7</th>\n",
       "      <th>8</th>\n",
       "      <th>9</th>\n",
       "      <th>10</th>\n",
       "      <th>...</th>\n",
       "      <th>193565</th>\n",
       "      <th>193567</th>\n",
       "      <th>193571</th>\n",
       "      <th>193573</th>\n",
       "      <th>193579</th>\n",
       "      <th>193581</th>\n",
       "      <th>193583</th>\n",
       "      <th>193585</th>\n",
       "      <th>193587</th>\n",
       "      <th>193609</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>userId</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>4.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>4.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>4.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>...</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>...</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>...</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>...</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>4.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>...</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>606</th>\n",
       "      <td>2.5</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>2.5</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>...</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>607</th>\n",
       "      <td>4.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>...</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>608</th>\n",
       "      <td>2.5</td>\n",
       "      <td>2.0</td>\n",
       "      <td>2.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>4.0</td>\n",
       "      <td>...</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>609</th>\n",
       "      <td>3.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>4.0</td>\n",
       "      <td>...</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>610</th>\n",
       "      <td>5.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>5.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>...</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>610 rows × 9724 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "movieId  1       2       3       4       5       6       7       8       \\\n",
       "userId                                                                    \n",
       "1           4.0     NaN     4.0     NaN     NaN     4.0     NaN     NaN   \n",
       "2           NaN     NaN     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "3           NaN     NaN     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "4           NaN     NaN     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "5           4.0     NaN     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "...         ...     ...     ...     ...     ...     ...     ...     ...   \n",
       "606         2.5     NaN     NaN     NaN     NaN     NaN     2.5     NaN   \n",
       "607         4.0     NaN     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "608         2.5     2.0     2.0     NaN     NaN     NaN     NaN     NaN   \n",
       "609         3.0     NaN     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "610         5.0     NaN     NaN     NaN     NaN     5.0     NaN     NaN   \n",
       "\n",
       "movieId  9       10      ...  193565  193567  193571  193573  193579  193581  \\\n",
       "userId                   ...                                                   \n",
       "1           NaN     NaN  ...     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "2           NaN     NaN  ...     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "3           NaN     NaN  ...     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "4           NaN     NaN  ...     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "5           NaN     NaN  ...     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "...         ...     ...  ...     ...     ...     ...     ...     ...     ...   \n",
       "606         NaN     NaN  ...     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "607         NaN     NaN  ...     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "608         NaN     4.0  ...     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "609         NaN     4.0  ...     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "610         NaN     NaN  ...     NaN     NaN     NaN     NaN     NaN     NaN   \n",
       "\n",
       "movieId  193583  193585  193587  193609  \n",
       "userId                                   \n",
       "1           NaN     NaN     NaN     NaN  \n",
       "2           NaN     NaN     NaN     NaN  \n",
       "3           NaN     NaN     NaN     NaN  \n",
       "4           NaN     NaN     NaN     NaN  \n",
       "5           NaN     NaN     NaN     NaN  \n",
       "...         ...     ...     ...     ...  \n",
       "606         NaN     NaN     NaN     NaN  \n",
       "607         NaN     NaN     NaN     NaN  \n",
       "608         NaN     NaN     NaN     NaN  \n",
       "609         NaN     NaN     NaN     NaN  \n",
       "610         NaN     NaN     NaN     NaN  \n",
       "\n",
       "[610 rows x 9724 columns]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data.pivot(index='userId', columns='movieId', values='rating')   # 这样会发现有大量的稀疏， 所以才会用字典进行存放"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-20T13:39:47.552252Z",
     "start_time": "2020-08-20T13:39:47.371208Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Split trainingSet and testSet success!\n",
      "TrainSet = 75593\n",
      "TestSet = 25243\n"
     ]
    }
   ],
   "source": [
    "# 声明两个字典， 分别是训练集和测试集\n",
    "trainSet, testSet = {}, {}\n",
    "trainSet_len, testSet_len = 0, 0\n",
    "pivot = 0.75    # 训练集的比例\n",
    "\n",
    "# 遍历data的每一行， 把userId, movidId, rating按照{user: {movidId: rating}}的方式存储， 当然定义一个随机种子进行数据集划分\n",
    "for ele in data.itertuples():   # 遍历行这里推荐用itertuples， 比iterrows会高效很多\n",
    "    user, movie, rating = getattr(ele, 'userId'), getattr(ele, 'movieId'), getattr(ele, 'rating')\n",
    "    if random.random() < pivot:\n",
    "        trainSet.setdefault(user, {})\n",
    "        trainSet[user][movie] = rating\n",
    "        trainSet_len += 1\n",
    "    else:\n",
    "        testSet.setdefault(user, {})\n",
    "        testSet[user][movie] = rating \n",
    "        testSet_len += 1\n",
    "\n",
    "print('Split trainingSet and testSet success!')\n",
    "print('TrainSet = %s' % trainSet_len)\n",
    "print('TestSet = %s' % testSet_len)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 计算用户之间的相似度\n",
    "这里用到了一个技巧， 我们知道， 计算出用户相似度来之后要存入到相似度矩阵里面， 所以这里先定义一个用户相似度矩阵来存放各个用户之间的相似度。 然后就是计算用户的相似度， 由于这里不涉及到评分问题（我们的任务是解决TopN推荐，即判断是不是用户要对电影打分）， 所以这里可以采用余弦相似度距离来计算用户之间的相似度。 余弦相似度求两个用户之间的过程如下：\n",
    "\n",
    "![](./images/1.png)\n",
    "\n",
    "这时候我们一般的思路就是遍历两遍用户表， 对于每两个不同的用户， 我们根据上面的计算公式去计算他们的相似度。 但是这时候， 时间复杂度是$O(|U|*|U|)$， 这在用户数很多的时候会非常耗时， 而事实上， 很多用户相互之间并没有对同样的物品产生过行为， 即**大部分情况下两个用户对同一物品打分的情况会很少很少**， 还记得上面的透视表吗？ 这时候我们可以换一种思路， 首先计算出两个用户对同一物品都打过分的用户对$(u, v)$, 然后对这种情况除以$\\sqrt{|N(u)||N(v)|}$。 这时候就需要建立物品到用户的倒排表， 对于每个物品都保存对该物品产生过行为的用户列表。 \n",
    "\n",
    "![](./images/2.png)\n",
    "\n",
    "这时候， 扫描一遍倒排表， 将用户列表中两两用户对应的那个位置元素进行累加统计， 就可以得到所有用户之间同时对同一物品发生行为的次数， 也就是余弦相似度的分子。比如上面的那个倒排表中， 首先建立一个$4*4$的用户相似度矩阵$W$，对于物品a， $W[A][B]$和$W[B][A]$加1， 对于物品b， 将$W[A][C]$和$W[C][A]$加1， 依次类推， 就可以得到最终的矩阵$W$。 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-20T14:56:13.964622Z",
     "start_time": "2020-08-20T14:56:11.802867Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Building movie-user table ...\n",
      "Build movie-user table success!\n",
      "Total movie number = 8765\n",
      "Build user co-rated movies matrix ...\n",
      "Build user co-rated movies matrix success!\n",
      "Calculating user similarity matrix ...\n",
      "Calculate user similarity matrix success!\n"
     ]
    }
   ],
   "source": [
    "user_sim_matrix = {}\n",
    "\n",
    "# 构建“电影-用户”倒排索引    # key = movidID,  value=list of userIDs who have seen this move\n",
    "print('Building movie-user table ...')\n",
    "movie_user = {}\n",
    "for user, movies in trainSet.items():   # 这里的user就是每个用户， movies还是个字典， {movieID: rating}\n",
    "    for movie in movies:       # 这里的movie就是movieID了\n",
    "        if movie not in movie_user:     # 如果movidID没在倒排索引里面\n",
    "            movie_user[movie] = set()  # 声明这个键的值是set， 保证用户不重复\n",
    "        movie_user[movie].add(user)     # 把用户加进去， 看上面的图就明白了\n",
    "print('Build movie-user table success!')\n",
    "\n",
    "\n",
    "# 下面建立用户相似矩阵\n",
    "movie_count = len(movie_user)\n",
    "print('Total movie number = %d' % movie_count)\n",
    "\n",
    "print('Build user co-rated movies matrix ...')\n",
    "for movie, users in movie_user.items():     # movid是movieID， users是set集合\n",
    "    for u in users:           # 对于每个用户， 都得双层遍历\n",
    "        for v in users:\n",
    "            if u == v:\n",
    "                continue\n",
    "            user_sim_matrix.setdefault(u, {})      # 把字典的值设置为字典的形式\n",
    "            user_sim_matrix[u].setdefault(v, 0)\n",
    "            user_sim_matrix[u][v] += 1     # 这里统计两个用户对同一部电影产生行为的次数， 这个就是余弦相似度的分母\n",
    "print('Build user co-rated movies matrix success!')\n",
    "\n",
    "# 下面计算用户之间的相似性\n",
    "print('Calculating user similarity matrix ...')\n",
    "for u, related_users in user_sim_matrix.items():\n",
    "    for v, count in related_users.items():    # 这里面v是相关用户， count是共同对同一部电影打分的次数\n",
    "        user_sim_matrix[u][v] = count / math.sqrt(len(trainSet[u]) * len(trainSet[v]))   # len 后面的就是用户对电影产生过行为的个数   \n",
    "print('Calculate user similarity matrix success!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 针对目标用户u， 找到其最相似的k个用户， 产生N个推荐\n",
    "得到用户的兴趣相似度后， UserCF算法会对用户推荐和他兴趣最相似的K个用户喜欢的物品。 下面公式度量了UserCF算法中用户u对物品i的感兴趣程度：\n",
    "$$p(u, i)=\\sum_{v \\in S(u, K) \\cap N(i)} w_{u v} r_{v i}$$\n",
    "其中， $S(u,k)$包含和兴趣u兴趣最接近的K个用户， $N(i)$是对物品i有过行为的用户集合， $w_{uv}$是用户u和用户v的兴趣相似度， $r_{vi}$代表用户v对物品i的兴趣， 因为使用单一行为的隐反馈数据， 所以这里$r_{vi}=1$<br><br>\n",
    "\n",
    "所以下面的代码逻辑是这样：\n",
    "* 首先， 给定我一个用户ID， 我先拿到这个用户ID目前看过的所有电影， 以防后面推荐重了。  \n",
    "* 然后从相似性矩阵中，找到与当前用户最相近的K个用户\n",
    "* 遍历他们看过的电影， 如果当前用户没有看过， 该电影的权重等级累加\n",
    "* 最后给所有的电影进行排序， 推荐前n部给当前用户"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-21T00:45:23.291461Z",
     "start_time": "2020-08-21T00:45:23.284480Z"
    }
   },
   "outputs": [],
   "source": [
    "# 找到最相似的20个用户， 产生10个推荐\n",
    "k = 20\n",
    "n = 10\n",
    "\n",
    "aim_user = 3      # 目标用户ID\n",
    "rank ={}\n",
    "watched_movies = trainSet[aim_user]      # 找出目标用户看到电影\n",
    "\n",
    "# 下面从相似性矩阵中找到与aim_user最相近的K个用户\n",
    "\n",
    "# v 表示相似用户， wuv表示相似程度\n",
    "for v, wuv in sorted(user_sim_matrix[aim_user].items(), key=lambda x: x[1], reverse=True)[0:k]:  # 字典按值从大到小排序， 相关性高到第\n",
    "    \n",
    "    # 把v用户看过的电影推荐给目标用户\n",
    "    for movie in trainSet[v]:\n",
    "        if movie in watched_movies:\n",
    "            continue\n",
    "        rank.setdefault(movie, 0)\n",
    "        rank[movie] += wuv\n",
    "    \n",
    "\n",
    "# 产生最后的推荐列表\n",
    "rec_movies = sorted(rank.items(), key=itemgetter(1), reverse=True)[:n]  # itemgetter(1) 是简洁写法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-21T00:45:35.163737Z",
     "start_time": "2020-08-21T00:45:35.158749Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(50, 0.7203832695490756),\n",
       " (318, 0.6420762634317767),\n",
       " (1097, 0.6146584283658186),\n",
       " (457, 0.603423178647777),\n",
       " (480, 0.5923937334471672),\n",
       " (1197, 0.5516471056998656),\n",
       " (1198, 0.5490620626206103),\n",
       " (527, 0.5487288351652937),\n",
       " (1196, 0.5453402293063451),\n",
       " (1210, 0.5388788288155224)]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rec_movies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 产生推荐之后， 通过准确率、召回率和覆盖率等进行评估。\n",
    "这里介绍评测指标：<br><br>\n",
    "1. 召回率<br>\n",
    "对用户u推荐N个物品记为$R(u)$, 令用户u在测试集上喜欢的物品集合为$T(u)$， 那么召回率定义为：\n",
    "$$\\operatorname{Recall}=\\frac{\\sum_{u}|R(u) \\cap T(u)|}{\\sum_{u}|T(u)|}$$\n",
    "这个意思就是说， 在用户真实购买或者看过的影片里面， 我模型真正预测出了多少， 这个考察的是模型推荐的一个全面性。 <br>\n",
    "\n",
    "2. 准确率<br>\n",
    "准确率定义为：\n",
    "$$\\operatorname{Precision}=\\frac{\\sum_{u} \\mid R(u) \\cap T(u)}{\\sum_{u}|R(u)|}$$\n",
    "这个意思再说， 在我推荐的所有物品中， 用户真正看的有多少， 这个考察的是我模型推荐的一个准确性。 <br><br>\n",
    "为了提高准确率， 模型需要把非常有把握的才对用户进行推荐， 所以这时候就减少了推荐的数量， 而这往往就损失了全面性， 真正预测出来的会非常少，所以实际应用中应该综合考虑两者的平衡。\n",
    "\n",
    "3. 覆盖率\n",
    "覆盖率反映了推荐算法发掘长尾的能力， 覆盖率越高， 说明推荐算法越能将长尾中的物品推荐给用户。\n",
    "$$\\text { Coverage }=\\frac{\\left|\\bigcup_{u \\in U} R(u)\\right|}{|I|}$$\n",
    "该覆盖率表示最终的推荐列表中包含多大比例的物品。如果所有物品都被给推荐给至少一个用户， 那么覆盖率是100%。\n",
    "\n",
    "4. 新颖度\n",
    "用推荐列表中物品的平均流行度度量推荐结果的新颖度。 如果推荐出的物品都很热门， 说明推荐的新颖度较低。  由于物品的流行度分布呈长尾分布， 所以为了流行度的平均值更加稳定， 在计算平均流行度时对每个物品的流行度取对数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-21T01:26:14.490677Z",
     "start_time": "2020-08-21T01:26:14.485690Z"
    }
   },
   "outputs": [],
   "source": [
    "# 这里先把产生推荐的那个封装成函数才能测试所有的测试样本\n",
    "def recommend(aim_user, k=20, n=10):\n",
    "    \n",
    "    rank ={}\n",
    "    watched_movies = trainSet[aim_user]      # 找出目标用户看到电影\n",
    "\n",
    "    # 下面从相似性矩阵中找到与aim_user最相近的K个用户\n",
    "\n",
    "    # v 表示相似用户， wuv表示相似程度\n",
    "    for v, wuv in sorted(user_sim_matrix[aim_user].items(), key=lambda x: x[1], reverse=True)[0:k]:  # 字典按值从大到小排序， 相关性高到第\n",
    "\n",
    "        # 把v用户看过的电影推荐给目标用户\n",
    "        for movie in trainSet[v]:\n",
    "            if movie in watched_movies:\n",
    "                continue\n",
    "            rank.setdefault(movie, 0)\n",
    "            rank[movie] += wuv\n",
    "    return sorted(rank.items(), key=itemgetter(1), reverse=True)[:n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-21T01:51:22.341674Z",
     "start_time": "2020-08-21T01:51:21.549192Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "precisioin = 0.3018\n",
      "recall = 0.0729\n",
      "coverage = 0.0430\n",
      "popularity = 4.7947\n"
     ]
    }
   ],
   "source": [
    "# 准确率、召回率和覆盖率\n",
    "hit = 0\n",
    "rec_count = 0     # 统计推荐的影片数量， 计算查准率\n",
    "test_count = 0    # 统计测试集的影片数量， 计算查全率\n",
    "all_rec_movies = set()    # 统计被推荐出来的影片个数， 无重复了， 为了计算覆盖率\n",
    "item_populatity = dict()   # 计算新颖度\n",
    "\n",
    "# 先计算每部影片的流行程度\n",
    "for user, items in trainSet.items():\n",
    "    for item in items.keys():\n",
    "        if item not in item_populatity:\n",
    "            item_populatity[item] = 0\n",
    "        item_populatity[item] += 1    # 这里统计训练集中每部影片用户观看的总次数， 代表每部影片的流行程度\n",
    "\n",
    "\n",
    "# 计算评测指标\n",
    "ret = 0\n",
    "ret_cou = 0\n",
    "for user, items in trainSet.items():    # 这里得保证测试集里面的用户在训练集里面才能推荐\n",
    "    \n",
    "    test_movies = testSet.get(user, {})\n",
    "    rec_movies = recommend(user)\n",
    "    for movie, w in rec_movies:\n",
    "        if movie in test_movies:\n",
    "            hit += 1\n",
    "        all_rec_movies.add(movie)\n",
    "        ret += math.log(1+item_populatity[movie])\n",
    "        ret_cou += 1\n",
    "    rec_count += n\n",
    "    test_count += len(test_movies)\n",
    "    \n",
    "    \n",
    "precision = hit / (1.0 * rec_count)\n",
    "recall = hit / (1.0 * test_count)\n",
    "coverage = len(all_rec_movies) / movie_count\n",
    "ret /= ret_cou*1.0\n",
    "    \n",
    "print('precisioin = %.4f\\nrecall = %.4f\\ncoverage = %.4f\\npopularity = %.4f' % (precision, recall, coverage, ret))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
